Crown reductions for the Minimum Weighted Vertex Cover problem

The paper studies crown reductions for the Minimum Weighted Vertex Cover problem introduced recently in the unweighted case by Fellows et al. [Blow-Ups, Win/Win's and crown rules: some new directions in FPT, in: Proceedings of the 29th International Workshop on Graph Theoretic Concepts in Computer Science (WG’03), Lecture notes in computer science, vol. 2880, 2003, pp. 1-12, Kernelization algorithms for the vertex cover problem: theory and experiments, in: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, Louisiana, January 2004, pp. 62-69]. We describe in detail a close relation of crown reductions to Nemhauser and Trotter reductions that are based on the linear programming relaxation of the problem. We introduce and study the so-called strong crown reductions, suitable for finding (or counting) all minimum vertex covers, or finding a minimum vertex cover under some additional constraints. It is described how crown decompositions and strong crown decompositions suitable for such problems can be computed in polynomial time. For weighted König-Egerváry graphs (G,w) we observe that the set of vertices belonging to all minimum vertex covers, and the set of vertices belonging to no minimum vertex covers, can be efficiently computed.Further, for some specific classes of graphs, simple algorithms for the MIN-VC problem with a constant approximation factor r<2 are provided. On the other hand, we conclude that for the regular graphs, or for the Hamiltonian connected graphs, the problem is as hard to approximate as for general graphs.It is demonstrated how the results about strong crown reductions can be used to achieve a linear size problem kernel for some related vertex cover problems.     

The structure of matrices with a maximum multiplicity eigenvalue

There is remarkable and distinctive structure among Hermitian matrices, whose graph is a given tree T and that have an eigenvalue of multiplicity that is a maximum for T. Among such structure, we give several new results: (1) no vertex of T may be “neutral”; (2) neutral vertices may occur if the largest multiplicity is less than the maximum; (3) every Parter vertex has at least two downer branches; (4) removal of a Parter vertex changes the status of no other vertex; and (5) every set of Parter vertices forms a Parter set. Statements (3), (4) and (5) are also not generally true when the multiplicity is less than the maximum. Some of our results are used to give further insights into prior results, and both the review of necessary background and the development of new structural lemmas may be of independent interest.     

Volumetric and infrared measurements on amorphous ice structure

We have simultaneously used adsorption isotherm volumetry and Fourier transform infrared spectroscopy in order to take the investigations on amorphous ice structure a step further, especially concerning porosity and annealing-induced modifications. We have studied surface reorganization during annealing and found that the number of surface sites decreases before crystallization, their relative ratios being different for amorphous and crystalline ice. We also present results confirming that ice can have a large specific surface area and nevertheless be non-microporous.     

On the reversed sub-martingale property of empirical discrepancies in arbitrary sample spaces

The empirical discrepancy is defined as a supremum over a class of functions of a collection of centered sample averages. For uncountable classes the discrepancy need not be measurable, and distributional assertions can become dependent on the structure of the underlying probability space. This paper shows that one such assertion—the reversed sub-martingale property—is valid when interpreted in terms of measurable cover functions for the canonical model, but that it can fail in other constructions of the underlying model.     

Several parameters of generalized Mycielskians

The generalized Mycielskians (also known as cones over graphs) are the natural generalization of the Mycielski graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer m?0, one can transform G into a new graph μ_m(G), the generalized Mycielskian of G. This paper investigates circular clique number, total domination number, open packing number, fractional open packing number, vertex cover number, determinant, spectrum, and biclique partition number of μ_m(G).     

A new family of proximity graphs: Class cover catch digraphs

Motivated by issues in machine learning and statistical pattern classification, we investigate a class cover problem (CCP) with an associated family of directed graphs—class cover catch digraphs (CCCDs). CCCDs are a special case of catch digraphs. Solving the underlying CCP is equivalent to finding a smallest cardinality dominating set for the associated CCCD, which in turn provides regularization for statistical pattern classification. Some relevant properties of CCCDs are studied and a characterization of a family of CCCDs is given.     

Examples of Calabi–Yau Threefolds as Covers of Almost-Fano Threefolds

We give a method for producing examples of Calabi–Yau threefolds as covers of degree d ≤ 8 of almost-Fano threefolds, computing explicitely their Euler– Poincaré characteristic. Such a method generalizes the well-knownclassical construction of Calabi–Yau threefolds as double covers of the projective space branched along octic surfaces.     

Effect of a Shock Pulse on a Floating Ice Sheet

The vibrations of a viscoelastic plate lying on an elastic liquid base subjected to pulse loading have been studied theoretically and experimentally. The effect of the variable depth of the reservoir, plate thickness, and strain relaxation time on the value of the plate vibration amplitude and the length and curvature of the flexural gravity wave profile are analyzed. Good agreement of theoretical and experimental results is obtained.     

激光除冰研究

架空输送电线路因覆冰而导致的事故危害性很大,本文总结了目前国内外输电线路导线覆冰的现状。统计国内外探索出来的各种预防,融化,除冰等很多解决方案。通过研究和探讨,分析导线覆冰的传热和能量,运用了多种激光器进行激光熔(除)冰实验,比较研究二氧化碳激光器的除冰情况。以及提出激光熔冰的方法、研究方向和前景。     

The complexity of minimum difference cover

The complexity of searching minimum difference covers, both in Z⁺ and in Z_n, is studied. We prove that these two optimization problems are NP-hard. To obtain this result, we characterize those sets—called extrema—having themselves plus zero as minimum difference cover. Such a combinatorial characterization enables us to show that testing whether sets are not extrema, both in Z⁺ and in Z_n, is NP-complete. However, for these two decision problems we exhibit pseudo-polynomial time algorithms.